nLab inclusion-exclusion

Redirected from "inclusion-exclusion principle".
The inclusion-exclusion principle

The inclusion-exclusion principle

Idea

The principle of inclusion and exclusion is essentially a sheaf condition for measures; it allows one to calculate the total measure of a space in terms of a cover. It applies also to cardinality, that is to counting measure.

Statement

Let XX be a measure space with measure μ\mu. Typical examples are a probability space or subprobability space, or an arbitrary set with counting measure. (In the latter case, we may let the measure take values in all cardinal numbers, so that the measure of a subset is its cardinality.)

Now let UU be a measurable finite cover of XX. (That is, we have a finite index set II and a function mapping an index jj in II to a measurable subspace U jU_j of XX, such that the union jU j\bigcup_j U_j of all of these subspaces is all of XX.) Then given any natural number kk and any kk-combination σ\sigma from II (a subset of II of cardinality kk), let the measure of σ\sigma be μ( jσU j)\mu(\bigcap_{j \in \sigma} U_j), the measure of the intersection of the subspaces assigned to the indexes in σ\sigma. We will call kk the size of the kk-combination σ\sigma. Note that for k=0k = 0 (so σ=\sigma = \empty), jU j=X\bigcap_{j \in \empty} U_j = X.

Theorem

The sum of the measures of the combinations of even size equals the sum of the measures of the combinations of odd size.

If we drop the requirement that UU be a cover of XX (that the union of UU be XX), we simply have that UU is a cover of the actual union of UU; the only difference is that the measure of the 00-combination is now the measure of this union instead of the measure of all of XX. Then the principle for small values of nn looks like this:

  • μ()=0\mu(\empty) = 0,
  • μ(A)=μ(A)\mu(A) = \mu(A),
  • μ(AB)+μ(AB)=μ(A)+μ(B)\mu(A \cup B) + \mu(A \cap B) = \mu(A) + \mu(B) (*),
  • μ(ABC)+μ(AB)+μ(AC)+μ(BC)=μ(A)+μ(B)+μ(C)+μ(ABC)\mu(A \cup B \cup C) + \mu(A \cap B) + \mu(A \cap C) + \mu(B \cap C) = \mu(A) + \mu(B) + \mu(C) + \mu(A \cap B \cap C),
  • etc.

If subtraction is available (as when μ\mu is a finite measure), we may solve for the first term on the left (the term from the 00-combination, that is the measure of the union):

  • μ()=0\mu(\empty) = 0,
  • μ(A)=μ(A)\mu(A) = \mu(A),
  • μ(AB)=μ(A)+μ(B)μ(AB)\mu(A \cup B) = \mu(A) + \mu(B) - \mu(A \cap B),
  • μ(ABC)=μ(A)+μ(B)+μ(C)μ(AB)μ(AC)μ(BC)+μ(ABC)\mu(A \cup B \cup C) = \mu(A) + \mu(B) + \mu(C) - \mu(A \cap B) - \mu(A \cap C) - \mu(B \cap C) + \mu(A \cap B \cap C),
  • etc.

The general formula is μ(A i1in)=(I)[1,n](1) |I|+1μ(iIA i)\mu(\underset{1 \le i \le n}{\bigcup A_{i}}) = \underset{(I \neq \emptyset)\subseteq [1,n]}{\sum}(-1)^{|I|+1}\mu(\underset{i \in I}{\bigcap}A_{i}).

This explains the term ‘inclusion-exclusion’; we are alternately adding (including) and subtracting (excluding) various intersections.

Proof

The proof is for all subspaces of a given measure space, by induction on the cardinality nn of the index set II. Although it is atypical, one may take, as one of the basic axioms of a measure, the formula (*), that is the inclusion-exclusion formula (on all measurable subspaces) for n=2n = 2; in any case, this is easy to prove. Then the formula for n>2n \gt 2 may be proved by induction. (The formula for n=0n = 0 is the axiom that the measure of the empty set is zero, and the formula for n=1n = 1 is trivial.)

As a definition of measure

The principle applies perfectly well to finitely additive measures (charges) taking values in any abelian monoid. On the other hand, the statement of inclusion-exclusion makes sense even when the cover UU is not finite; and if we require it whenever UU is countable, then we force the measure to be countably additive. If we require inclusion-exclusion for arbitrary (even uncountable) UU, then we get the definition of a normal measure.

In constructive mathematics, the inclusion-exclusion principle fails in that μ\mu may satisfy μ(AB)=μ(A)μ(B)\mu(A \cup B) = \mu(A) \cup \mu(B) when AA and BB are disjoint without necessarily satisfying (*). On the other hand, we may adopt (*) as the proper clause in the definition of measure. For measures on a Cheng space (which is the best established constructive theory of measure in general), inclusion-exclusion follows from finite additivity (for disjoint sets) and the principle that intersection with full sets (which are specified for a Cheng space before any measure is given) preserves measure, so in that sense it makes no difference which axiom we take. But (*) is not valid constructively for cardinality in general; counting measure is a Cheng measure only on sets with decidable equality.

In both cases, we see that we can adopt the principle of inclusion-exclusion (which ultimately is motivated by cardinality of finite sets) as the only principle necessary to define what we mean by a measure (although we must already have a measurable space to define it on).

Last revised on February 6, 2023 at 03:23:58. See the history of this page for a list of all contributions to it.